package codingforgreat.lchot150;

import java.util.Arrays;

public class Lc300 {
    public int lengthOfLIS1(int[] nums) {
        return process(nums,0,Integer.MIN_VALUE);
    }
    public int process(int[] nums,int index,int n){
        if(index == nums.length){
            return 0;
        }
        int p1 = process(nums,index + 1,n);
        int res = 0;
        int p2 = 0;
        if(nums[index] > n){
            p2 =  process(nums,index + 1,nums[index]) + 1;
        }
        return Math.max(p1,p2);
    }
    public int lengthOfLIS2(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        for(int i = 0;i < nums.length;i++){
            for(int j = 0;j < i;j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
        }
        int res = 0;
        for(int i = 0;i < dp.length;i++){
            res = Math.max(dp[i],res);
        }
        return res;
        // return process(nums,0,Integer.MIN_VALUE);
    }
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        if(nums.length == 1){
            return 1;
        }
        int[] dp = new int[nums.length];
        int[] end = new int[nums.length];
        end[0] = nums[0];
        int right = 0;
        int max = 1;
        for(int i = 1;i < nums.length;i++){
            int l = 0;
            int r = right;
            //二分在end中找到小于等于nums[i]的数
            while(l <= r){
                int mid = (l + r) / 2;
                if(nums[i] <= end[mid]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }
            right = Math.max(right,l);
            end[l] = nums[i];
            max = Math.max(max,l + 1);
        }
        return max;
    }
}
